const INF = Number.MAX_SAFE_INTEGER;

const Colors = {
    Green: 0,
    Grey: 1,
    Red: 2,
    Black: 3
}

class Vertex {
    constructor(id, x, y, color = Colors.Green) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.color = color;
    }
}

class Edge {
  constructor(srcId, dstId, weight, color = Colors.Black) {
    this.srcId = srcId;
    this.dstId = dstId;
    this.weight = weight;
    this.color = color;
  }
}

class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected;
    this.vertices = new Map(); // id -> Vertex
    this.adjList = new Map();  // id -> set(Edge(), Edge())
  }

  addVertex(v) {
    if (!this.vertices.has(v.id)) {
      this.vertices.set(v.id, v);
      this.adjList.set(v.id, new Map()); // initialize adjacency list with map;
    }
  }

  addEdge(srcId, dstId, weight) {
    if(!this.checkExistence(srcId, dstId)) return;
    let edge = new Edge(srcId, dstId, weight);
    this.adjList.get(srcId).set(dstId, edge);
    if (this.isDirected !== true) {
      this.adjList.get(dstId).set(srcId, edge);
    }
  }

  getEdge(srcId, dstId) {
    if(!this.checkExistence(srcId, dstId)) return null;

    return this.adjList.get(srcId).get(dstId);
  }

  getWeight(srcId, dstId) {
    if(!this.checkExistence(srcId, dstId)) return;
    if(!this.adjList.get(srcId).has(dstId)) {
        return INF;
    } else {
        return this.adjList.get(srcId).get(dstId).weight;
    }
  }

  checkExistence(srcId, dstId) {
    if (!this.adjList.get(srcId)) {
        console.error(`vertex with id ${srcId} does not exist`);
        return false;
    }
    if (!this.adjList.get(dstId)) {
        console.error(`vertex with id ${dstId} does not exist`);
        return false;
    }
    return true;
  }

  getVertices() {
    return this.vertices.keys();
  }

  getNeighbors(srcId) {
    return this.adjList.get(srcId);
  }

  getAdjList() {
    return this.adjList;
  }

  getVertex(id) {
      return this.vertices.get(id);
  }

  toString() {
    let s = '';
    this.vertices.keys().forEach(srcId => {
        s += `${this.vertices[srcId].id} -> `;
        const neighbors = this.adjList.get(srcId);
        neighbors.keys().forEach(dstId=> {
            s += `${dstId} : ${neighbors.get(dstId).weight} `;
        });
        s += '\n';
    });
    return s;
  }
}

function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min) + min); //The maximum is exclusive and the minimum is inclusive
}

function generateRandomGraphInCanvas(numNodes, numEdges, width, height) {
    let g = new Graph(false); // 无向图

    g.addVertex(new Vertex(0, 100, 130));
    g.addVertex(new Vertex(1, 300, 90));
    g.addVertex(new Vertex(2, 430, 230));
    g.addVertex(new Vertex(3, 550, 110));
    g.addVertex(new Vertex(4, 360, 310));
    g.addVertex(new Vertex(5, 130, 430));
    g.addVertex(new Vertex(6, 600, 410));
    g.addVertex(new Vertex(7, 260, 200));

    g.addEdge(0, 1, 5);
    g.addEdge(0, 5, 9);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 12);
    g.addEdge(1, 3, 15);
    g.addEdge(1, 7, 4);
    g.addEdge(2, 3, 3);
    g.addEdge(2, 6, 11);
    g.addEdge(3, 6, 9);
    g.addEdge(4, 2, 1);
    g.addEdge(4, 6, 13);
    g.addEdge(5, 4, 4);
    g.addEdge(5, 6, 20);
    g.addEdge(5, 7, 5);
    g.addEdge(7, 2, 7);
    g.addEdge(7, 4, 6);
    return g;
}